//数组、矩阵与广义表
#include <stdio.h>
#include <stdlib.h>
#define maxSize 4
//#define n 5//定义宏常量

int main(int argc, char *argv[]) { // 列  行
	//二维数组的 行优先、列优先 储存————以A[6][10]为例
	//若按 行优先————先把行塞满，再变动列————A[3][5]是第 10*3+6个元素
	//若按 列优先————先把列塞满，再变动行————A[3][5]是第 6*5+4个元素
	int m,n;
	//矩阵————实质为一个 二维数组
	int A[m][n];
	int B[n][m];//定义一个B 作为A的 转置
			
}
/***矩阵***/
//矩阵的转置操作————A[m][n]->B[n][m]
void transposeMatrix(int A[][maxSize],int B[][maxSize],int m,int n)
{
	for(int i=0;i<m;i++)
		for(int j=0;j<n;j++)
			B[j][i] = A[i][j];//为B赋值
}

//矩阵的相加操作————C[m][n] = A[m][n]+B[m][n]
void addMatrix(int A[][maxSize],int B[][maxSize],int C[][maxSize],int m,int n)
{
	for(int i=0;i<m;i++)
		for(int j=0;j<n;j++)
			C[i][j] = A[i][j]+B[i][j];
}

//矩阵的相乘操作————A[m][n]*B[n][k] = C[m][k]
void multiplyMatrix(int A[][maxSize],int B[][maxSize],int C[][maxSize],int m,int n,int k)
{
	for(int i=0;i<m;i++)
		for(int j=0;j<k;j++)//遍历C[m][k]的各个元素，准备为其赋值
	{
		C[i][j] = 0;
		for(int p=0;p<n;p++)//为C[m][k]的各个元素 赋值
			C[i][j] += A[i][p]*B[p][j];
	}
}

/*特殊矩阵————在一维数组中的存储*/
//对称矩阵————只需要存储下三角部分——按行优先的顺序，存储到一维数组中
//三角矩阵————按行优先的顺序，存储到一维数组中，最后 再存储常数c


/**稀疏矩阵**/
//稀疏矩阵————没有规律的矩阵————将它的信息全部存于 一维数组中

/**
	稀疏矩阵的顺序存储结构：
				包括 三元组表示法、伪地址表示法
**/
				
/*三元组表示法*/
//矩阵中的每一个元素，包含三个信息————数值、行下标、列下标
						//————要都存储于一维数组中————可以构造一个新的数据类型triple（存储三个信息），创建一个triple数组
						/*————还可以trimat[maxSize+1][3],前面表示元素的索引，后面存储值、行标、列标
								float trimat[maxSize+1][3];//可以存储小数——数值
								(int)trimat[m][1];
								(int)trimat[m][2];//引用行、列
								
								第 0 行存储 非零元素个数、行数、列数
						*/
//构造triple数组法
typedef struct
{
	int val;//数值
	int line,row;//列，行
}triple;
//二维数组储存

//构造对应的三元组————给定一个稀疏矩阵（float）型A————存储非零元素
void createTrimat(float A[][maxSize],int m,int n,float B[][3])
{
	int k = 1;//要存储的元素个数————即非零元素个数————多出一个空间，作为 0 行
	for(int i=0;i<m;i++)
		for(int j=0;j<n;j++)//遍历A矩阵
			if(A[i][j]!=0)
	{
		B[k][0] = A[i][j];
		B[k][1] = i;
		B[k][2] = j;
		k++;
	}//将信息存储进 B
	
	//完善 0 行
	B[0][0] = k-1;
	B[0][1] = m;
	B[0][2] = n;
}

//通过三元组B——打印矩阵A
void printMatrix(float B[][3])
{
	int k = 1;//跟踪B 中的元素
	for(int i=0;i<B[0][1];i++)
		for(int j=0;j<B[0][2];j++)
	{
		if(i==(int)B[k][1]&&j==(int)B[k][2])//找到第k个 非零元素
			{
				printf("%lf ",B[k][0]);
				k++;//瞄准下一个非零元素
			}
		else//其余为 0 元素
			printf("0 ");
	}
}

/*伪地址表示法*/
//存储A[m][n]中的非零元素————构建一个二维数组weiStation[][2]：前一个位 存储数值 ； 后一个位 存储地址 A[i][j]——>n*i+j


/**
稀疏矩阵的链式存储结构：
包括 邻接表表示法、十字链表表示法
**/

/*邻接表表示法*/
/*要存储A[m][n]中的非零元素
	————构造m个链表，每个链表存储 一个行 所有的非零元素
	————结点中包含：指针、数值、列标
*/

/*十字链表表示法*/
/*要存储A[m][n]中的非零元素
	————构造m个链表，每个链表存储 一个行 所有的非零元素————头结点在最左边————不存储数值，地址（-1，-1）
	————构造n个链表，每个链表存储 一个列 所有的非零元素————头结点在最上边————不存储数值，地址（-1，-1）
	————将行链表、列链表相连， 构造成十字链表————整个十字链表的头结点 在左上角————存储 非零元个数、行数、列数
	————结点中包含：向右指针、向下指针、数值、行标、列标
*/
//十字表普通结点的定义
typedef struct crossNode
{
	int row,col;//存储行标、列标
	float val;//存储数值
	struct crossNode *right,*down;//指向右的指针、指向下的指针
}crossNode;

//十字表头结点的定义
typedef struct crossList
{
	int m,n,k;//存储行数、列数、非零元个数
	struct crossNode *right,*down;//指向两头结点的指针
}crossList;

//用十字链表M——储存A[m][n]的k个非零元素
void createCrossList(float A[][maxSize],int m,int n,crossList M)
{
	int k = 0;//存储非零元个数
	if(M.right)
		free(M.right);
	if(M.down)
		free(M.down);//初始化M，去除原有链接
	M.m = m;
	M.n = n;//存储行、列数
	
	M.right = (crossNode *)malloc(sizeof(crossNode)*n);//为 各列链表 的头结点开辟空间
	//创造各列链表的辅助指针————用来链接 各结点————先指向各列链表的 头结点
	crossNode *col[n];
	for(int i=0;i<n;i++)
		col[i] = &M.right[i];
	
	M.down = (crossNode *)malloc(sizeof(crossNode)*m);//为 各行链表 的头结点开辟空间
	//创造各行链表的辅助指针————用来链接 各结点————先指向各行链表的 头结点
	crossNode *row[m];
	for(int i=0;i<m;i++)
		row[i] = &M.down[i];

	for(int i=0;i<m;i++)
		for(int j=0;j<n;j++)
			if(A[i][j]!=0)
	{		//找到要存储的数据
		crossNode *p =  (crossNode *)malloc(sizeof(crossNode));//为新结点开辟一个空间
		p->val = A[i][j];
		p->row = i;
		p->col = j;//存储基本数据
		
		col[j]->down = p;
		col[j] = col[j]->down;
		row[i]->right = p;
		row[i] = row[i]->right;//将p链接到十字表中, 改变辅助指针，方便下一次链接
	}
}

/***广义表***/
//一种线性表————可以储存各种各样的 元素————该元素可以是一种数据，还可以是另一广义表
/*
A = (a,b)
B = (A,c) = ((a,b),c)
广义表的长度————最上层 元素的个数，B的长度为2
广义表的深度————表中括号的 最大层数，B的深度为2

表头————广义表的 第一个元素
表尾————除首元素的 其余元素

存储结构————详见书本
*/